package warm100;

import java.util.PriorityQueue;

public class findKthLargest_215 {

    /**
     * 优先队列
     */
    public int findKthLargest1(int[] nums, int k) {
        //就是在 for 循环里面判断小顶堆里面的 size() 是否大于 k 个数，是的话就 poll() 出去；
        //整个 for 循环结束之后剩下来的就是 k 个数的小顶堆。堆顶即第 k 大的数。
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.add(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.peek();
    }

    public int findKthLargest(int[] nums, int k) {
        boolean min_max;  //是否建立大根堆
        int len = nums.length;
        min_max = k < len / 2;
        k = min_max ? k : len - k + 1;
        //不需要真的构造一个堆，将数组作为堆即可
        //初始化堆
        for (int j = len / 2 - 1; j >= 0; j--) { //将所有分支节点为根节点的树倒序处理一遍
            if (min_max)
                init_max(nums, j, len, true);
            else
                init_min(nums, j, len, true);
        }
        //输出k-1次堆顶元素
        while (k-- != 1) {
            //尾节点放到堆顶，size-1
            nums[0] = nums[--len];  //输出一次，长度减1
            if (min_max)
                init_max(nums, 0, len, false);
            else
                init_min(nums, 0, len, false);
        }
        return nums[0];
    }


    /**
     * 以k位置为根节点的树处理为大根堆
     *
     * @param nums 堆
     * @param k    根节点位置
     * @param len  堆大小
     * @param flag flag  是否为初始化，初始化时左右孩子都要处理
     */
    private void init_max(int[] nums, int k, int len, boolean flag) {
        //叶子节点(没有左孩子) 无需处理
        if (2 * (k + 1) > len) return;
        int left_index = 2 * k + 1;   //左孩子坐标
        int right_index = 2 * k + 2 == len ? k : 2 * k + 2;//右孩子坐标越界时，设为自己不影响下面计算
        int index = 0;
        //根节点小于一个或者两个孩子
        if (nums[k] < Math.max(nums[left_index], nums[right_index])) {
            //更大的孩子的坐标
            index = nums[left_index] > nums[right_index] ? left_index : right_index;
            //交换
            int temp = nums[k];
            nums[k] = nums[index];
            nums[index] = temp;
        }
        //处理左孩子
        if (flag) {
            init_max(nums, left_index, len, true);
            if (2 * k + 2 < len)
                init_max(nums, 2 * k + 2, len, true);
        } else
            //此时为输出后调整，一定发生了互换
            init_max(nums, index, len, true);
    }

    /**
     * 以k位置为根节点的树处理为大根堆
     *
     * @param nums 堆
     * @param k    根节点位置
     * @param len  堆大小
     * @param flag flag  是否为初始化，初始化时左右孩子都要处理
     */
    private void init_min(int[] nums, int k, int len, boolean flag) {
        //叶子节点(没有左孩子) 无需处理
        if (2 * (k + 1) > len) return;
        int left_index = 2 * k + 1;   //左孩子坐标
        int right_index = 2 * k + 2 == len ? k : 2 * k + 2;  //右孩子坐标越界时，设为自己不影响下面计算
        int index = 0;
        //根节点大于一个或者两个孩子
        if (nums[k] > Math.min(nums[left_index], nums[right_index])) {
            //更小的孩子的坐标
            index = nums[left_index] < nums[right_index] ? left_index : right_index;
            //交换
            int temp = nums[k];
            nums[k] = nums[index];
            nums[index] = temp;
        }
        //处理左孩子
        if (flag) {
            init_min(nums, left_index, len, true);
            if (2 * k + 2 < len)
                init_min(nums, 2 * k + 2, len, true);
        } else
            //此时为输出后调整，一定发生了互换
            init_min(nums, index, len, true);
    }


    /**
     * 标准建立大根堆
     */
    public int findKthLargest2(int[] nums, int k) {
        int len = nums.length;
        // 构建大根堆
        for (int i = len / 2 - 1; i >= 0; i--)
            adjustHeap(nums, i, len);
        //输出k-1次堆顶元素
        while (k-- != 1) {
            //尾节点放到堆顶，size-1
            nums[0] = nums[--len];  //输出一次，长度减1
            adjustHeap(nums, 0, len);
        }
        return nums[0];
    }

    /**
     * 以k位置为根节点的树处理为大根堆
     * @param arr  堆
     * @param i     根节点位置
     * @param len 堆大小
     */
    private static void adjustHeap(int[] arr, int i, int len) {
        int temp = arr[i];   //保存当前父节点的值，无需每一层都交换
        for (int j = i * 2 + 1; j < len; j = j * 2 + 1) {  // i * 2 + 1 是 i 的左子节点的索引。
            // j = j * 2 + 1  即进入下一层继续调整
            // j 为 子节点
            if (j + 1 < len && arr[j] < arr[j + 1])      //存在右孩子且有孩子更大，则 j 指向右子节点。
                j++;
            if (arr[j] > temp) {  //与父节点比较
                arr[i] = arr[j];      // 子节点上移
                i = j;                    // 父节点指针下移到子节点位置
            } else {        //若子节点均不大于temp，说明已满足大顶堆，终止循环
                break;
            }
        }
        arr[i] = temp;      //停止下移父节点都后，将当前子节点赋值父节点的值
    }
}